//归并排序：分治思想，平分数组，分别排序，用递归，重点：合并函数    性能：稳定，时间复杂度：
//Ta = Tb + Tc + K(K是将子问题b、c合并成问题a的时间) 所以，T1 = C(n=1)  Tn = 2*T(n/2) + n;  n表示合并函数的时间复杂度O（n）
// 进一步分解：Tn = 2^k * T(n/2^k) + k*n   T(n/2^k) = T1  k = log2n, 带入k，得到：Tn = Cn + nlog2n      故此得到时间复杂度：O(nlogn)
//不是原地排序，空间复杂度O（n），高，致命弱点，
const mergeArr = (left, right) => {
    let temp = [];
    let indexL = 0;
    let indexR = 0;
    while (left.length > indexL && right.length > indexR) {
        if (left[indexL] > right[indexR]) {
            temp.push(right[indexR]);
            indexR++;
        } else {
            temp.push(left[indexL]);
            indexL++;
        }      
    }
        return temp.concat(right.slice(indexR)).concat(left.slice(indexL));
}

//归并排序
const mergeSort = (arr) => {
    if (arr.length <= 1) {
        return arr;
    }
    //拆分数组
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return mergeArr(mergeSort(left), mergeSort(right));
}